/*
 * @lc app=leetcode.cn id=1155 lang=typescript
 *
 * [1155] 掷骰子的N种方法
 */

// @lc code=start
function numRollsToTarget(d: number, f: number, target: number): number {
  const mod = 1000000007;
  // dp[i][j] 表示掷骰子 i 个，目标值为 j 的方案数
  const dp: number[][] = new Array(d + 1).fill(0).map(() => new Array(target + 1).fill(0));
  // 边界条件，0个骰子，目标值为 0 的方案数为 1
  dp[0][0] = 1;

  for (let i = 1; i <= d; i++) {
    for (let j = 1; j <= target; j++) {
      for (let k = 1; k <= f; k++) {
        // 计算最后一个骰子需要投掷的点数
        if (j < k) break;
        dp[i][j] += dp[i - 1][j - k];
        dp[i][j] %= mod;
      }
    }
  }

  return dp[d][target];
}
// @lc code=end
